use crate::collections::chain::ChainBase;
use crate::collections::common::{max, min};

pub trait HeapBase<T> {
    fn new() -> Self;
    fn push(&mut self, val: T);
    fn pop(&mut self) -> Option<T>;
    fn size(&self) -> u64;
    fn value(&self) -> Option<T>;
    fn update(&mut self, val: Option<T>);
}

pub struct MinHeap<C>(C);

pub struct MaxHeap<C>(C);

impl<T: Clone + Ord, C: ChainBase<T>> HeapBase<T> for MaxHeap<C> {
    #[inline]
    fn new() -> Self {
        MaxHeap(C::new())
    }

    #[inline]
    fn push(&mut self, val: T) {
        self.0.push(val.clone());
        let (mut i, mut j) = (self.0.size() / 2, self.0.size());
        while i > 0 && self.0.at(i - 1).unwrap() < val {
            self.0.swap(i - 1, j - 1);
            j = i;
            i = j / 2;
        }
    }

    #[inline]
    fn pop(&mut self) -> Option<T> {
        if self.0.size() > 0 {
            self.0.swap(0, self.0.size() - 1);
            let value = self.0.pop();
            self.update(None);
            return value;
        }
        None
    }

    #[inline]
    fn size(&self) -> u64 {
        self.0.size()
    }

    #[inline]
    fn value(&self) -> Option<T> {
        self.0.at(0)
    }

    #[inline]
    fn update(&mut self, val: Option<T>) {
        if self.0.size() > 0 {
            if let Some(v) = val {
                self.0.update(0, v)
            }
            let val = self.0.at(0);
            let (mut i, mut j, size) = (1, 2, self.0.size());
            while j <= size {
                let (v_j, mj) = match j < size {
                    true => max(self.0.at(j - 1), j, self.0.at(j), j + 1),
                    false => (self.0.at(j - 1), j),
                };
                if v_j > val {
                    self.0.swap(i - 1, mj - 1);
                    i = mj;
                    j = mj * 2;
                } else {
                    break;
                }
            }
        }
    }
}

impl<T: Clone + Ord, C: ChainBase<T>> HeapBase<T> for MinHeap<C> {
    #[inline]
    fn new() -> Self {
        MinHeap(C::new())
    }

    #[inline]
    fn push(&mut self, val: T) {
        self.0.push(val.clone());
        let (mut i, mut j) = (self.0.size() / 2, self.0.size());
        while i > 0 && self.0.at(i - 1).unwrap() > val {
            self.0.swap(i - 1, j - 1);
            j = i;
            i = j / 2;
        }
    }

    #[inline]
    fn pop(&mut self) -> Option<T> {
        if self.0.size() > 0 {
            self.0.swap(0, self.0.size() - 1);
            let value = self.0.pop();
            self.update(None);
            return value;
        }
        None
    }

    #[inline]
    fn size(&self) -> u64 {
        self.0.size()
    }

    #[inline]
    fn value(&self) -> Option<T> {
        self.0.at(0)
    }

    #[inline]
    fn update(&mut self, val: Option<T>) {
        if self.0.size() > 0 {
            if let Some(v) = val {
                self.0.update(0, v)
            }
            let val = self.0.at(0);
            let (mut i, mut j, size) = (1, 2, self.0.size());
            while j <= size {
                let (v_j, mj) = match j < size {
                    true => min(self.0.at(j - 1), j, self.0.at(j), j + 1),
                    false => (self.0.at(j - 1), j),
                };
                if v_j < val {
                    self.0.swap(i - 1, mj - 1);
                    i = mj;
                    j = mj * 2;
                } else {
                    break;
                }
            }
        }
    }
}

//leftist heap
//krew heap
